package org.regotto.basics.doublePointer;

import java.util.HashMap;

/**
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 */
public class N3LongestSubstrWithoutRepeatChar {

    public static void main(String[] args) {
        System.out.println(new N3LongestSubstrWithoutRepeatChar().lengthOfLongestSubstring("abcabcbb"));
    }

    /**
     * 双指针解法, 存在重复的字符移动慢指针, 求出在不重复的情况下最大
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int res = 0;
        for (int i = 0, j = 0; i < s.length(); i++) {
            if (!map.containsKey(s.charAt(i))) map.put(s.charAt(i), 1);
            else map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
            while (map.get(s.charAt(i)) > 1) {
                map.put(s.charAt(j), map.get(s.charAt(j++)) - 1);
            }
            res = Math.max(res, i - j + 1);
        }
        return res;
    }

}
